/*
 * 本关任务：编写能对给定n个叶子结点，构建哈夫曼树，给出每个叶子结点对应编码的程序。
 * input:7 9 6 2 3 7 10 8
 * output :9 00
10 01
2 1000
3 1001
6 101
7 110
8 111
 */
/*请在此处编写代码，完成哈夫曼编码，并能输出每个叶子结点的编码*/
/**********  Begin  *********/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node{
    int w;
    int parent,lchild,rchild;
};
struct httree{
    int m;
    int root;
    struct node * ht;
};
struct Huffman{
    int len;
    char n[20];
    int u;

}s[100];
struct httree* htree(int a[],int n){
    struct httree* p=(struct httree*)malloc(sizeof(struct httree));
    p->ht=(struct node *)malloc(sizeof(struct node )*(2*n-1));
    for(int i=0;i<2*n-1;i++){
        p->ht[i].lchild=-1;
        p->ht[i].rchild=-1;
        p->ht[i].parent=-1;
        if(i<n)p->ht[i].w=a[i];
        else p->ht[i].w=-1;
    }
    int m1,m2,x1,x2;
    for(int i=0;i<n-1;i++){
        m1=10000;
        m2=10000;
        x1=-1;
        x2=-1;
        for(int j=0;j<n+i;j++){
            if(p->ht[j].w<m1&&p->ht[j].parent==-1){
                m2=m1;
                x2=x1;
                m1=p->ht[j].w;
                x1=j;
            }
            else if(p->ht[j].w<m2&&p->ht[j].parent==-1){
                m2=p->ht[j].w;
                x2=j;
            }
        }

        p->ht[x1].parent=n+i;
        p->ht[x2].parent=n+i;
        p->ht[n+i].w=m1+m2;
        p->ht[n+i].lchild=x1;
        p->ht[n+i].rchild=x2;
    }
    p->root=2*n-2;
    return p;

}

int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    struct httree* p=htree(a,n);

    for(int i=0;i<n;i++){
        int b[100]={0};
        int t=0;
        int k=p->ht[i].parent;
        if(p->ht[k].lchild==i)b[t]=1;
        else b[t]=2;
        t++;
        while(k!=2*n-2){
            if(p->ht[p->ht[k].parent].lchild==k)b[t]=1;
            else b[t]=2;
            t++;
            k=p->ht[k].parent;
        }
        s[i].u=p->ht[i].w;
        s[i].len=t;
        for(int x=0,j=t-1;j>=0;x++,j--)
            s[i].n[x]=b[j];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(strcmp(s[i].n,s[j].n)==-1){
                struct Huffman q=s[i];
                s[i]=s[j];
                s[j]=q;
            }
        }
    }
    for(int i=0;i<n;i++){
        printf("%d ",s[i].u);
        for(int j=0;j<s[i].len;j++)printf("%d",s[i].n[j]-1);
        printf("\n");
    }
}



/**********  End  *********/

